﻿// 0828train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <deque>

using namespace std;

/*
 其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标
 如果没有满足条件的 j ，你将没有任何折扣
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格

输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
 */

vector<int> finalPrices(vector<int>& prices)
{
    //逆序遍历，最后一个商品没有折扣
    //while(stack_vec.back()>prices[i])stack_vec.pop_back()
    vector<int>stack_vec;
    int vec_size = prices.size();
    vector<int>result(vec_size);

    for (int i=vec_size-1; i>=0; i--)
    {
        int curr_num = prices[i];

        while (!stack_vec.empty() && stack_vec.back()> curr_num)
        {
            stack_vec.pop_back();
        }

        if (!stack_vec.empty() && stack_vec.back()<=curr_num)
        {
            result[i] = curr_num - stack_vec.back();
        }
        else
        {
            result[i] = curr_num;
        }

        //比curr_num大的数已弹出，curr_num直接入栈
        stack_vec.push_back(curr_num);
        //for------
    }

    return result;

    //finalPrices
}


/*
输入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
输出：3

解释：
从 10（速度为 2）和 8（速度为 4）开始的车会组成一个车队，它们在 12 相遇。车队在 target 形成。
从 0（速度为 1）开始的车不会追上其它任何车，所以它自己是一个车队。
从 5（速度为 1） 和 3（速度为 3）开始的车组成一个车队，在 6 相遇。车队以速度 1 移动直到它到达 target
*/
int carFleet(int target, vector<int>& position, vector<int>& speed) {
    /*
     最简单的思路，排序，A B，只要A车到达终点时间快于B车，一定可以形成车队
     所以，A>stack.top()，无法形成车队，所以A压栈
     */
    int vec_size = position.size();
    vector<pair<int, int>>pos_vec;
    for (int i=0; i<vec_size; i++)
    {
        pos_vec.push_back(make_pair(position[i],speed[i]));
    }

    sort(pos_vec.begin(), pos_vec.end(), [](pair<int, int>& a, pair<int,int>&b)
        {
            return a.first < b.first;
        });

    //计算时间AB 如果A_time<=B_time, A一定可以追上B,A不用入队
    //相等可以追上，两车会在终点相遇

    vector<double>stack_vec;
    for (int i=vec_size-1; i>=0; i--)
    {
        double arrive_time = double(target - pos_vec[i].first) / double(pos_vec[i].second);

        if (!stack_vec.empty() && arrive_time>stack_vec.back())
        {
            stack_vec.push_back(arrive_time);
        }

        if (stack_vec.empty())
        {
            stack_vec.push_back(arrive_time);
        }
    }
    return stack_vec.size();
    //carFleet
}

/*
 寿司店周年庆，正在举办优惠活动回馈新老客户寿司转盘上总共有n盘寿司，
 prices[i]是第 i 盘寿司的价格，
 如果客户选择了第 i盘寿司，寿司店免费赠送客户距离第 i 盘寿司最近的下一盘寿司 j
 前提是prices[j] < prices[i]，如果没有满足条件的 j，则不赠送寿司
每个价格的寿司都可无限供应

输入描述
输入的每一个数字代表每盘寿司的价格，每盘寿司的价格之间使用空格分隔
寿司的盘数 n范围为: 1 <= n <= 500
输出描述
输出享受优惠后的一组数据，每个值表示客户选择第i 盘寿司时实际得到的寿司的总价格。使用空格进行分隔

输入
3 15 6 14
输出
3 21 9 17
 */

class Solution01
{
public:
    Solution01(vector<int>&origin_vec)
    {
        int origin_size = origin_vec.size();
        //解决环的问题
        vector<int>ring_vec(2 * origin_size);
        for (int i=0; i<ring_vec.size(); i++)
        {
            ring_vec[i] = origin_vec[i % origin_size];
        }

        vector<int>stack_vec;
        //prices[j] < prices[i]
        for (int i=ring_vec.size()-1; i>=0; i--)
        {
            int curr_num = ring_vec[i];
            while (!stack_vec.empty() && stack_vec.back()>=curr_num)
            {
                stack_vec.pop_back();
            }

            if (!stack_vec.empty())
            {
                //实际总价格，当前价格+赠送价格
                ring_vec[i] += stack_vec.back();
            }
            stack_vec.push_back(curr_num);
        }

        for (int i=0; i<origin_size; i++)
        {
            cout << ring_vec[i] << ' ';
        }

	    //Solution01
    }
};


/*
 M (1 <= M <= 20)辆车需要在一条不能超车的单行道到达终点
 起点到终点的距离为N (1 <= N <= 400)
速度快的车追上前车后，只能以前车的速度继续行驶，求最后一车辆到达目的地花费的时间
注:每辆车固定间隔1小时出发，比如第一辆车0时出发，第二辆车1时出发，依次类推

输入描述
第一行两个数字：M N分别代表车辆数和到终点的距离，以空格分隔。
接下来M行，每行1个数字 S，代表每辆车的速度。0 < S < 30

输出描述
输出：最后一辆车到达目的地花费的时间。
保留一位小数

输入
2 11
3
2
输出
5.5
 */

/*
 0时speed 3出发
 1时speed 2出发
 */

class Solution02
{
public:
    Solution02(vector<double>&speed_vec, double distance)
    {
        double max_time = -1;

        //到达时刻D/speed_i + i
        for (int speed_i = 0; speed_i<speed_vec.size(); speed_i++)
        {
            double curr_time = (distance / speed_vec[speed_i]) + speed_i;
            max_time = max(max_time, curr_time);
        }

        double start_time = speed_vec.size() - 1;
        double cost_time = max_time - start_time;
        cout << fixed << setprecision(1) << cost_time;
    	//Solution02
    }
};


/*
 100个人从1开始依次报数，报到为M的人自动退出圈圈
 然后下一个人接着从1开始报数，直到剩余的人数小于M
请问最后剩余的人在原先的编号为多少？

输入描述
输入一个整数参数 M

输出描述
如果输入参数M小于等于1或者大于等于100，输出“ERROR!”；
否则按照原先的编号从小到大的顺序，以英文逗号分割输出编号字符串

示例1
3
输出
58,91

4
输出
34,45,97
 */
class Solution03
{
public:
    Solution03(int out_num)
    {
        //小于等于1或者大于等于100，输出“ERROR!”
        if (out_num<=1 || out_num>=100)
        {
            cout << "ERROR!";
            return;
        }

        int total = 100;
        deque<int>num_queue;

        for (int i=1; i<=total; i++)
        {
            num_queue.push_back(i);
        }

        int curr_count = 1;
        while (num_queue.size()>=out_num)
        {
            int curr_node = num_queue.front();
            num_queue.pop_front();

            if (curr_count!=out_num)
            {
                num_queue.push_back(curr_node);
                curr_count += 1;
            }
            else
            {
                curr_count = 1;

                if (num_queue.size() == out_num - 1)
                    break;
            }
        }

        vector<int>sort_vec;
        for (auto&num:num_queue)
        {
            sort_vec.push_back(num);
        }

        sort(sort_vec.begin(), sort_vec.end());

        for (int i=0; i<sort_vec.size(); i++)
        {
            cout << sort_vec[i];
            if (i!=sort_vec.size()-1)
            {
                cout << ',';
            }
        }
	    //Solution03
    }
};


int main()
{
	{
        //int out_num = 4;
        int out_num;
        cin >> out_num;
        Solution03 solu(out_num);

        return 0;
	}
	{
/*
2 11
3
2
*/
        int vec_size, distance;
        cin >> vec_size >> distance;

        vector<double>speed_vec(vec_size);
        for (int i=0; i<vec_size; i++)
        {
            cin >> speed_vec[i];
        }

        Solution02 solu(speed_vec, distance);

        return 0;
	}
	{
        vector<int>num_vec;
        //string input = "3 15 6 14"; //3 21 9 17
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;
        while (oh_sstream>>token)
        {
            num_vec.push_back(stoi(token));
        }
        Solution01 solu(num_vec);

        return 0;
	}
	{
        //target = 27, 
        //target = 100, position = [0,2,4], speed = [4,2,1] 1
        //target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] 3
        int target = 17;
        vector<int>position = { 8,12,16,11,7 }, speed = { 6,9,10,9,7 };

        
        cout << carFleet(target, position, speed);

        return 0;
	}
    //prices = [8,4,6,2,3]
    vector<int>prices = { 8,4,6,2,3 };

    vector<int>result = finalPrices(prices);

    for (auto&num:result)
    {
        cout << num << ' ';
    }

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
